/*
 * @lc app=leetcode.cn id=310 lang=cpp
 *
 * [310] 最小高度树
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        std::vector<std::vector<int>> neighborTable(n);
        std::vector<int> degree(n, 0);
        for (auto& edge : edges) {
            neighborTable[edge[0]].emplace_back(edge[1]);
            neighborTable[edge[1]].emplace_back(edge[0]);
            degree[edge[0]] += 1;
            degree[edge[1]] += 1;
        }
        int remainNodeNum = n;
        // min height tree num <= 2
        while (remainNodeNum > 2) {
            // delete nodes (degree = 1)
            std::vector<int> deleteNodeIndexVec;
            for (int i=0;i<n;++i) {
                if (degree[i] == 1) {
                    deleteNodeIndexVec.emplace_back(i);
                }
            }

            remainNodeNum -= deleteNodeIndexVec.size();
            for (int index : deleteNodeIndexVec) {
                degree[index] = -1;
                for (int neighbor : neighborTable[index]) {
                    degree[neighbor] -= 1;
                }
            }
        }

        std::vector<int> result;
        for (int i=0;i<n;++i) {
            printf("%d ", degree[i]);
            if (degree[i] >= 0) {
                result.emplace_back(i);
            }
        }
        return result;
    }
private:
    // floyd : get max dis, need n^2 memory, n^3 time, get all dis but useless
    // Topological sort : wow ~
    // dfs : how to
    // bfs : violent
};
// @lc code=end

// 6\n[[0,1],[0,2],[0,3],[3,4],[4,5]]